#include<iostream>
#include<assert.h>
#include<initializer_list>
#include<algorithm>
using namespace std;

//warning: 
/*
1.插入数据时需要先检查容量  
2.插入/删除数据都需要更新_finish的位置 
3.删除数据时需要断言防止容器为空
4.[]需要判断下标的合法性
5.注意迭代器失效的问题 --->  扩容之后原来的迭代器就失效了！！！  或者迭代器的意义发生改变 
	(reserve函数:需要提前保存size的大小 和erase函数:返回删除位置的下一个位置的迭代器)
*/
namespace Mango
{
template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	
	//凡是构造函数都需要把三个指针成员初始化为空！！
	vector() 	:_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{}
	
	//一次插入n个相同的值
	//由于知道插入的个数为n，为了防止插入时反复扩容，所以建议先开辟好空间
	vector(size_t n, const T& val) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		reserve(n);
		for(size_t i = 0;i<n;i++)
		{
			push_back(val);
		}
	}
	//上述的函数需要重载成员函数，否则该语句会被认为是迭代器构造初始化 vector<int> v(3,2);
	vector(int n, const T& val) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		reserve(n);
		for(int i = 0;i<n;i++)
		{
			push_back(val);
		}
	}
	vector(long n, const T& val) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		reserve(n);
		for(size_t i = 0;i<n;i++)
		{
			push_back(val);
		}
	}
	
	template<class InputIterator>
	vector(InputIterator first,InputIterator last) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		while(first != last)
		{
			push_back(*first);
			first++;
		}
	}
	
	vector(const initializer_list<T>& lt) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		//写法1:
		for(auto& x:lt)
		{
			push_back(x);
		}
		//写法2:这里要取initializer_list<T>的内置类型，而T还没有实例化,所以要加typename告诉编译器后面的是个类型
		//typename initializer_list<T>::iterator it = lt.begin();
//		auto it = lt.begin();
//		while(it != lt.end())
//		{
//			push_back(*it);
//			it++;
//		}
	}
	
	//传统写法
	vector(const vector<T>& v)  :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		cout << "vector(const vector<T>& v)" << endl;
		reserve(v.capacity());//开辟和v同样容量的空间
		//然后遍历容器v的数据插入到当前容器
		//err写法: memcpy(_start,v._start,sizeof(T)*v.size()); 原因:memcpy是按字节拷贝==>浅拷贝  对于内置类型,即高效也没有问题,但是对于有资源管理的自定义类型会存在问题
		//要实现深拷贝
		for(int i = 0;i<v.size();i++)
		{
			_start[i] = v[i]; //对于自定义类型,比如string，会去调用它自己的operator= 是深拷贝
		}
		//处理指针的关系
		_finish = _start + v.size();
		_endofstorage = _start + v.capacity();
	}
	//现代写法:
//	vector(const vector<T>& v)  :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
//	{
//		cout << "vector(const vector<T>& v)" << endl;
//		//构造出一个临时对象，然后两个容器进行交换
//		vector<T> tmp(v.begin(),v.end()); //复用迭代器构造一个临时对象
//		swap(tmp);
//	}
	vector(vector<T>&& v) :_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
	{
		cout << "vector(vector<T>&& v)" << endl;
		swap(v); // 移动构造,直接进行资源的转移
	}
	
	//传统写法
	vector<T>& operator=(const vector<T>& v)
	{
		cout << "vector<T>& operator=(vector<T>& v)" << endl;
		if(this != &v)
		{
			delete[] _start;
			//不能使用reserve,因为reserve当中要判断是否需要扩容,n > capacity() 
			//而capacity的计算方式为指针-指针,但是现在_start指向的空间已经释放了,_start是空指针,不能再使用,所以只能new一块空间
			_start = new T[v.capacity()];  
			for(int i = 0 ; i < v.size();i++)
			{
				_start[i] = v[i];
			}
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
		}
		return *this;
	}
//	//现代写法:
//	vector<T>& operator=(const vector<T>& v)
//	{
//		cout << "vector<T>& operator=(vector<T>& v)" << endl;
//		if(this != &v)
//		{
//			vector<T> tmp(v.begin(),v.end());
//			swap(tmp);
//		}
//		return *this;
//	}
	vector<T>& operator=(vector<T>&& v)
	{
		cout <<  "vector<T>& operator=(vector<T>&& v)" << endl;
		swap(v);
		return *this;
	}
	
	
	~vector()
	{
		if(_start)
		{
			delete[] _start;
		}
		_start = _finish = _endofstorage = nullptr;
	}
	
	//指针-指针的前提是：两个指针指向的是同一块连续的空间
	size_t size() const
	{ 
		return _finish - _start;//指针-指针 ==> 二者相差的元素的个数
	}
	size_t capacity() const 
	{
		return _endofstorage - _start;
	}
	
	bool empty() const
	{
		return _start == _finish;
	}
	void swap(vector<T>& v)
	{
		::swap(_start,v._start);
		::swap(_finish,v._finish);
		::swap(_endofstorage,v._endofstorage);
	}
	
	//迭代器相关函数
	iterator begin()
	{
		return _start;
	}
	iterator end()
	{
		return _finish;
	}
	const_iterator begin() const 
	{
		return _start;
	}
	const_iterator end() const 
	{
		return _finish;
	}
	
	//[]
	T& operator[](size_t pos)
	{
		assert(pos < size());
		return _start[pos];
	}
	const T& operator[](size_t pos) const 
	{
		assert(pos < size());
		return _start[pos];
	}
	
	void insert(iterator pos,const T& val)
	{
    //保证pos位置的合法性
    assert(pos >= _start);
    assert(pos <= _finish);
	  //插入需要检查是否需要扩容
    if(_start == _finish)
    {
      int newaCapacity = capacity() == 0 ? 10 : capacity() * 2;
      reserve(newaCapacity);
    }
    //把pos及其后面的数据 往后移动
    iterator end = _finish -1;
    while(end >= pos)
    {
      *(end+1) = *end;
      end--;
    }
    *pos = val;
    _finish++;
	}
	void pop_back()
	{
		assert(!empty());
		_finish--;
	}
	iterator erase(iterator pos) //返回删除位置的下一个位置的迭代器
	{
    //容器不能为空
		assert(!empty());
    //保证pos位置的合法性
    assert(pos >= _start);
    assert(pos < _finish); //_finish位置不能删除
		iterator cur = pos +1 ;
		while(cur != end()) //end()迭代器==》 _finish
		{
			*(cur-1) = *(cur);
			cur++;
		}
		--_finish; //删除了数据需要更新_finish
		return pos;
	}
	void resize(int n ,const T& val = T())
	{
	  //扩充元素/缩小元素个数
    if(n < size())
    {
      _finish = _start + n;
    }
    else 
    {
      //判断是否需要扩容
      if(n > capacity())
      {
        reserve(n);
      }
      //填充元素
      while(_finish != _start + n)
      {
        *_finish = val;
        _finish++;
      }
    }
	}
	void reserve(int n)
	{
		//先检查是否是扩容
		if(n > capacity())
		{
			T* tmp = new T[n];
			//把原来的数据拷贝
			int sz = size();//先记录size()的大小
			for(int i = 0;i<size();i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start; //即使最初_start为空也没问题,因为delete nullptr不会报错
			_start = tmp;
			//Bug:
			//_finish = _start + size(); //err,因为size的计算方式为: _start - _finish 更新了_start之后,二者已经不指向同一块空间
			//解决办法:先记录size()的大小
			_finish = _start + sz;
			_endofstorage = _start + n;
		}
	}
	
	void push_back(const T& val)
	{
		//先检查是否需要扩容
		if(_start == _finish)
		{
			int newCapacity = capacity() == 0 ? 10:capacity() * 2;
			reserve(newCapacity);
		}
		*_finish = val;
		_finish++;
	}

	//后序补充的函数：
	T& at(size_t pos)
	{
		if(pos >= size())
		{
			throw out_of_range("vector:at");
		}
		return _start[pos];
	}

	const T& at(size_t pos) const
	{
		if(pos >= size())
		{
			throw out_of_range("vector:at");
		}
		return _start[pos];
	}

	void clear() //清空vector的内容==>本质是把_finish指针移动到_start位置
	{
		_finish = _start;
	}
	T& front()
	{
		assert(!empty());
		//return _start[0];
		return *begin();
	}
	
	const T& front() const
	{
		assert(!empty());
		return *begin();
	}

	T& back()
	{
		assert(!empty());
		//return _start[size()-1];
		auto it = end();
		return *(--it);
	}

	const T& back() const
	{
		assert(!empty());
		//return _start[size()-1];
		auto it = end();
		return *(--it);
	}
private:
	iterator _start;
	iterator _finish;
	iterator _endofstorage;
};

void test_vector1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);

    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";//1 2 3 4 5 6
    }
    cout << endl;

    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";//1 2 3 4 5 6
        ++it;
    }
    cout << endl;

    for (auto e : v)
    {
        cout << e << " ";//1 2 3 4 5 6
    }
    cout << endl;
}


void test_vector3()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    vector<int> v2(v1);
    for (auto e : v2)
        cout << e << " ";//1 2 3 4
    cout<<endl;

    vector<int> v3;
    v3.push_back(10);
    v3.push_back(20);
    v3.push_back(30);

    v1 = v3;
    for (auto e : v1)
        cout << e << " ";//10 20 30
    cout << endl;
}

void test_vector4()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
    if (it != v1.end())
    {
        // 如果insert中发生了扩容，那么会导致it指向空间被释放
        // it本质就是一个野指针，这种问题，我们就叫迭代器失效
        v1.insert(it, 20);
    }

    for (auto e : v1)
    {
        cout << e << " ";//1 20 2 3 4
    }
    cout<<endl;
}

void test_vector5()
{
    // 三种场景去测试
    // 1 2 3 4 5 -> 正常
    // 1 2 3 4   -> 崩溃
    // 1 2 4 5   -> 没删除完
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(4);
    v1.push_back(5);
	
     for (auto e : v1)
        cout << e << " "; //1 2 4 5
    
    // 要求删除v1所有的偶数
    vector<int>::iterator it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)
            it = v1.erase(it);
        else
            ++it;
    }   
  
    for (auto e : v1)
        cout << e << " "; //1 5
    cout << endl;
}

void test_vector6()
{
    vector<string> v;
    v.push_back("111111111111111111111111");
    v.push_back("111111111111111111111111");
    v.push_back("1111111111");
    v.push_back("1111111111");
    v.push_back("1111111111");

    for (auto& e : v)
    {
        cout << e <<endl;
    }
    cout<<endl;
}
}
